package com.guangyunl.f_array;

import java.util.Scanner;

// 二分查找
public class Demo03Binary {
    public static void main(String[] args) {
        Demo02Bubble demo02Bubble = new Demo02Bubble();
        // 输入创建数组的长度
        System.out.print("请输入要创建的数组的长度:");
        Scanner scanner = new Scanner(System.in);
        int arrLength = scanner.nextInt();
        // 创建数组
        int[] arr3 =  Demo02Bubble.createArray(arrLength);
        // 给数组排序
        arr3 = Demo02Bubble.bubbleSort(arr3);
        // 输出数组
        demo02Bubble.printArray(arr3);
        System.out.print("请输入需要查找的数据: ");
        // 需要查找的数
        int number = scanner.nextInt();
        Demo03Binary demo03Binary = new Demo03Binary();
        // 定义被查找数的下标 -1 代表该数组中不存在该数据
        int index = -1;
        // 被查找数的下标
        index = demo03Binary.binarySearch01(number,arr3);

        if(index == -1){
            System.out.println(number + " 在数组中不存在");
        }else{
            System.out.println(number + " 的下标为: " + index);
        }
        // 被查找数的下标
        index = demo03Binary.binarySearch02(number,arr3);

        if(index == -1){
            System.out.println(number + " 在数组中不存在");
        }else{
            System.out.println(number + " 的下标为: " + index);
        }
    }

    // 二分查找 for循环
    public int binarySearch01(int number, int[] arr){
        // 定义被查找数的下标 -1 代表该数组中不存在该数据
        int index = -1;
        for (int min = 0,max = arr.length-1,mid = (min+max)/2; min <= max ;) {
            if(number > arr[mid]){
                min = mid+1;
                mid = (min+max)/2;
            }else if(number < arr[mid]){
                max = mid-1;
                mid = (min+max)/2;
            }else if(number == arr[mid]){
                index = mid;
                return index;
            }else {
                return index;
            }
        }
        return index;
    }

    // 二分查找 while循环
    public int binarySearch02(int number, int[] arr){
        // 定义被查找数的下标 -1 代表该数组中不存在该数据
        int index = -1;
        // 定义三个变量，分别代表最大索引，最小索引，中间索引
        int max = arr.length-1;
        int min = 0;
        int mid = 0;
        // 查找
        while(min<=max){
            mid = (min+max)/2;
            if(number > arr[mid]){
                min = mid+1;
            }else if(number < arr[mid]){
                max = mid-1;
            }else if(number == arr[mid]){
                index = mid;
                return index;
            }else {
                return index;
            }
        }
        return index;
    }
}
/*
请输入要创建的数组的长度:11
数组为 = [ 3, 8, 8, 15, 21, 25, 33, 49, 55, 70, 93 ]
请输入需要查找的数据: 8
8 的下标为: 2
8 的下标为: 2
 */
/*
请输入要创建的数组的长度:11
数组为 = [ 7, 13, 21, 25, 28, 67, 67, 84, 85, 90, 94 ]
请输入需要查找的数据: 67
67 的下标为: 5
67 的下标为: 5
 */
/*
请输入要创建的数组的长度:11
数组为 = [ 8, 28, 31, 41, 54, 59, 66, 74, 81, 92, 95 ]
请输入需要查找的数据: 66
66 的下标为: 6
66 的下标为: 6
 */
